A rather easy yet rigorous proof of a version of G\"odel's firstincompleteness theorem is presented. The version is "each recursivelyenumerable theory of natural numbers with 0, 1, +, *, =, logical and, logicalnot, and the universal quantifier either proves a false sentence or fails toprove a true sentence". The proof proceeds by first showing a similar result ontheories of finite character strings, and then transporting it to naturalnumbers, by using them to model strings and their concatenation. Proof systemsare expressed via Turing machines that halt if and only if their input stringis a theorem. This approach makes it possible to present all but one parts ofthe proof rather briefly with simple and straightforward constructions. Thedetails require some care, but do not require significant background knowledge.The missing part is the widely known fact that Turing machines can performcomplicated computational tasks.
展开▼
